﻿#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <map>
#include <assert.h>
#include<vector>
using namespace std;
#include "AVLTree.h"

//int main() {
//	multimap<string, string> dict;//全部可以插入
//	dict.insert(make_pair("left", "左边"));
//	dict.insert(make_pair("left", "剩余"));
//	dict.insert(make_pair("left", "左边"));
//
//	//map<string, string> dict;//只能插入第一个 "左边"
//	//dict.insert(make_pair("left", "左边"));
//	//dict.insert(make_pair("left", "剩余"));//修改value要使用[]
//	for (auto& kv : dict)
//		cout << kv.first << ":" << kv.second << endl;
//	return 0;
//}



//测试AVLTree
//int main() {
//	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
//	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };//涉及双旋
//	AVLTree<int, int> t;
//	for (auto e : a)
//		t.Insert(make_pair(e, e));//value可以是任意数据，这里value和key相同，只是为了方便演示。
//	t.InOrder();
//	cout << t.IsBalance() << endl;
//	return 0;
//}


//进一步测试AVLTree
int main() {
	const int N = 1000000;
	vector<int> v;
	v.reserve(N);
	srand((unsigned int)time(0));

	for (size_t i = 0; i < N; i++)
		v.push_back(rand() + i);

	size_t begin2 = clock();
	AVLTree<int, int> t;
	for (auto e : v)
		t.Insert(make_pair(e, e));
	size_t end2 = clock();

	cout << t.IsBalance() << endl;
	cout << t.Height() << endl;
	cout << t.Size() << endl;

	size_t begin1 = clock();
	for (auto e : v)
		t.Find(e);
	size_t end1 = clock();
	cout << "Find:" << end1 - begin1 << endl;
	cout << "Insert:" << end2 - begin2 << endl;

	//如果有问题可以用下面的方式调试
	//const int N = 20;
	//vector<int> v;
	//v.reserve(N);
	////srand((unsigned int)time(0));//屏蔽这行只生成一次随机数

	//for (size_t i = 0; i < N; i++) {
	//	v.push_back(rand());
	//	cout << v.back() << endl;
	//}

	//AVLTree<int, int> t;
	//for (auto e : v) {
	//	if (e == 14604)
	//		int x = 0;//这样没意义，只是为了打断点，空语句不能打断点

	//	t.Insert(make_pair(e, e));
	//	cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	//}
	//cout << t.IsBalance() << endl;
	return 0;
}